package someTestExcemple.huaweiOd.container.stack;

//华为OD机试 - 简单的解压缩算法 - 栈（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/130892757
import java.util.*;
//创建一个栈Stack来辅助还原原始字符串；
//        使用一个指针i遍历压缩字符串；
//        当前字符为左花括号{时，将其入栈；
//        当前字符为字母时，将其转换为字符串并压入栈；
//        当前字符为数字时，找到连续的数字字符，并将其转换为整数time；
//        弹出栈顶元素，重复time次并拼接成字符串add；
//        将生成的add入栈；
//        当前字符为右花括号}时，依次弹出栈顶元素，直到遇到左花括号{，将弹出的元素拼接成字符串add并入栈；
//        将栈内元素依次弹出并拼接，得到最终的原始字符串；
public class DecompressAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        sc.close();
        Stack<String> stack = new Stack<>();

        int n = line.length();
        // 2、使用一个指针i遍历压缩字符串
        int i = 0;
        while (i < n) {
            char c = line.charAt(i);
            // 3、当前字符为左花括号{时，将其入栈；
            if (c == '{') {
                stack.push(String.valueOf(c));
                i++;
                // 4、当前字符为字母时，将其转换为字符串并压入栈；
            } else if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
                stack.push(String.valueOf(c));
                i++;
                // 5、当前字符为数字时，找到连续的数字字符，并将其转换为整数time；
            } else if (c >= '0' && c <= '9') {
                int j = i;
                while (j < n && line.charAt(j) >= '0' && line.charAt(j) <= '9') {
                    j++;
                }

                int time = Integer.parseInt(line.substring(i, j));
                String pop = stack.pop();
                String add = "";
                // 6、弹出栈顶元素，重复time次并拼接成字符串add；
                for (int p = 0; p < time; p++) {
                    add += pop;
                }
                // 7、将生成的add入栈；
                stack.push(add);
                i = j;
            } else {
                String add = "";
                // 8、当前字符为右花括号}时，依次弹出栈顶元素，直到遇到左花括号{，将弹出的元素拼接成字符串add并入栈；
                while (!stack.isEmpty()) {
                    String pop = stack.pop();
                    if (pop.equals("{")) {
                        break;
                    }
                    add = pop + add;
                }
                stack.push(add);
                i++;
            }
        }

        String ret = "";
        // 9、将栈内元素依次弹出并拼接，得到最终的原始字符串；
        while (!stack.isEmpty()) {
            ret = stack.pop() + ret;
        }
        System.out.println(ret);
    }
}
